package week02

// 106. 从中序与后序遍历序列构造二叉树
// https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

// 从前序遍历可以知道根节点
// 从中序遍历可以知道左右子树节点数量

// 中序：左中右
// 后序：左右中
// 中：[9,3,15,20,7]
// 后：[9,15,7,20,3]
// 后序遍历最后一个节点是根节点
// 从中序遍历中可以知道左右子树各自的节点数量

func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}

	var node = &TreeNode{}
	node.Val = postorder[len(postorder)-1]

	var rootIndex = 0
	for i, val := range inorder {
		if val == node.Val {
			rootIndex = i
			break
		}
	}
	// 注意：根节点不在任意一棵子树中
	var leftNodes = inorder[:rootIndex]
	var rightNodes = inorder[rootIndex+1:]
	// 找左子树根节点
	for i := len(postorder)-2; i >= 0; i-- {
		if isInSlice(postorder[i], leftNodes) {
			node.Left = buildTree(leftNodes, postorder[:i+1])
			break
		}
	}
	// 找右子树根节点
	for i := len(postorder)-2; i >= 0; i-- {
		if isInSlice(postorder[i], rightNodes) {
			node.Right = buildTree(rightNodes, postorder[:i+1])
			break
		}
	}
	return node
}

func isInSlice(val int, sli []int) bool {
	for _, v := range sli {
		if val == v {
			return true
		}
	}
	return false
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}